208E - Blood Cousins - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define AM17 ios_base::sync_with_stdio(false),cin.tie(NULL);
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
#define Ones(n) __builtin_popcount(n)
#define lenSorts(s) sort(s.begin(), s.end(), [&] (const string &s, const string &t) { return s.size() < t.size();});
int dx4[4] = { -1, 0, 1, 0 };
int dy4[4] = { 0, 1, 0, -1 };
int dx8[] = {+0, +0, -1, +1, +1, +1, -1, -1};
int dy8[] = {-1, +1, +0, +0, +1, -1, +1, -1};
string Dir = "URDL";
template <class T>
istream & operator>> (istream&is , vector<T> &v )
{
    for (auto &i:v)
        is>> i ;
    return is ;
}
template <class T>
ostream & operator<< (ostream&os ,const vector<T> &v )
{
    for (auto &i:v)
        os << i << " " ;
    os << '\n' ;
    return os ;
}
const int Mod=1e9+7,N=1e5+10,LOG=20;
vector<int>adj[N],depth[N];
int up[N][LOG],level[N],in[N],out[N],vis[N];
int t=0;
void dfs(int node,int parent)
{
    level[node]=level[parent]+1;
    in[node]=++t;
    up[node][0]=parent;
    depth[level[node]].push_back(t);
    vis[node]= 1;
    for (int i=1;i<LOG;i++)
    {
        up[node][i]=up[up[node][i-1]][i-1];
    }
    for (auto child:adj[node])
    {
        if(child==parent)
            continue;
        dfs(child,node);
    }
    out[node]=++t;
}
int KthAnc(int u,int k)
{
    for (int i=LOG-1;i>=0;i--)
    {
        if((1<<i)&k)
            u=up[u][i];
    }
    return u;
}
//
//int LCA(int u,int v)
//{
//    if(level[u]<level[v])
//        swap(u,v);
//    int k=level[u]-level[v];
//    u = KthAnc(u,k);
//    if(u==v)
//        return u;
//    for (int i=LOG-1;i>=0;i--)
//    {
//        if(up[u][i]==up[v][i])
//            continue;
//        u=up[u][i];
//        v=up[v][i];
//    }
//    return up[u][0];
//}
int solve(int v,int p)
{
   if((level[v]-1)<p)
       return 0;
   int u= KthAnc(v,p);

   int d=level[v];
   int l= lower_bound(depth[d].begin(),depth[d].end(),in[u])-depth[d].begin();
   int r= lower_bound(depth[d].begin(),depth[d].end(),out[u])-depth[d].begin();

    return r-l;

}
int main()
{
    AM17

    int loop=1,cnt=1;
//    cin>>loop;
    while (loop--)
    {
        int n,q;
        cin>>n;
        for (int i=1;i<=n;i++)
        {
            int p;
            cin>>p;
            if(p)
                adj[p].push_back(i);
        }
        for (int i=1;i<=n;i++)
        {
            if(!vis[i])
                dfs(i,i);
        }
        cin>>q;
        while (q--)
        {
            int v,p;
            cin>>v>>p;
            int ans=solve(v,p);
            cout<<(ans?ans-1:0)<<" ";
        }

    }

}